A Computer Program Listing Appendix containing the following files:
testclass.java 3 KB
wordgraph.java 17 KB
edge.java 1 KB
line.java 2 KB
digraph.java 4 KB
node.java 1 KB
tempEdge.java 1 KB
tempNode.java 1 KB
on two identical copies of compact discs created on Jul. 16, 2002 for application Ser. No. 09/104,909 is hereby incorporated by reference.
The present invention relates in general to the field of automated graph drawing and display.
Complex systems are being used with increasing frequency. Examples of complex systems include a highway system connecting cities, a telephone system providing communication connections among a group of businesses with telephone, computers, fax machines and beepers, and a genealogical family tree. Complex systems are also used in the organization of distributed data base information systems and artificial neural networks.
These complex systems each can be described, explained and illustrated as a collection of objects and connecting paths between selected pairs of the objects. The mathematical model for these systems is a directed graph. A directed graph, G=(V,E), is defined by a set and a collection: a finite set, V, of elements (also referred to as xe2x80x9cnodesxe2x80x9d) and a finite collection, E, of elements of ordered pairs of nodes (also referred to as xe2x80x9cedgesxe2x80x9d). Each ordered pair of nodes comprises an initial node and a terminal node. With directed graphs, an edge is xe2x80x9cincident out ofxe2x80x9d its initial node and is xe2x80x9cincident intoxe2x80x9d its terminal node.
An xe2x80x9cincidence listxe2x80x9d for a directed graph is a list of all the edges that are incident into or incident out of each node of the directed graph. An xe2x80x9cincident outxe2x80x9d list for a node is a subset of the incidence list containing the edges which are incident out of that node. Likewise, an xe2x80x9cincident inxe2x80x9d list for a node is a subset of the incidence list containing the edges which are incident into that node.
FIG. 1 is an illustration of one representation of a directed graph 10, with the nodes labeled n1, n2, n3, etc. and the edges labeled e1, e2, e3, etc. As shown, a node is represented by a circle and an edge is represented by a line segment or arc segment between two nodes. The initial node and terminal node of the edge are distinguishable by the edge""s xe2x80x9corientationxe2x80x9d represented by an arrow on the edge pointing from the initial node to the terminal node.
The comprehension of a complex system from its representative pictorial representation of its representative directed graph is relatively easy when the graph contains on1y a few nodes and few edges (i.e., G has a small number of elements). However, when the number of nodes or the number of edges is great, the resulting dense directed graph and the represented system becomes difficult to understand. Additionally, a visual representation of a dense directed graph is not easily rendered for display on computer output devices nor is it convenient to electronically transmit such a graph. These problems have been associated with dense directed graphs of static information, and even more problems exist where the complex system is dynamic.
Examples of system models which can be represented mathematically by directed graphs include data flow diagrams, subroutine-call graphs, program nesting trees, object-oriented class hierarchies, class interfaces and entity-relationship (ER) diagrams for software engineering, matrix organizational charts, use-case diagrams, process flow charts for business process management, petri nets and state transition diagrams for real-time system modeling, PERT charts and activity trees for decision support systems, knowledge-representation (KR) diagrams, conceptual graphs, Bayesian networks, concept charts, semantic networks and associative networks for artificial intelligence and knowledge representation, SLD-trees for logic programming, concept lattices for medical science, evolutionary trees for biology, molecular drawings for chemistry, family trees for. genealogy and network diagrams for communications theory and network engineering.
There are numerous ways to model and render complex systems that share the concepts of directed graphs. The nodes of directed graphs generally represent atomic or elemental concepts or things. Terms such as entity or element are analogous to a directed graph node indicating indivisibility or at least unique identity. The edges of directed graphs represent associations, relationships, paths, links or connections between pairs of nodes and those terms are used interchangeably with directed graph edges depending on the model.
Because of the combinatorial and geometric nature of the systems modeled and the wide array of application domains, research on graph drawing has been conducted in such diverse areas such as discrete mathematics (topological graph theory, geometric graph theory, order theory), algorithmics (graph algorithms, data structures, computational geometry) and human-computer interaction (visual languages, graphical user interfaces, software visualization). For an example of the rich literature available on the subject of graph drawing see xe2x80x9cAlgorithms for Drawing Graphs: An Annotated Bibliographyxe2x80x9d, Computer Geometric Theory and Applications, G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis 4(5):235-282 (1994), which is incorporated by reference herein for all purposes.
Much effort has gone into developing better, faster, more readable and newer ways to draw, present, use, traverse, search and understand graphs, including arbitrary directed graphs.
Practitioners in fields dealing with complex systems strive to recognize, define, arrange and depict, according to some system, the elementary concepts and relationships between these elementary concepts derived from observation, study, experimentation, design and agreement. For example, biological taxonomists strive to agree on the classification of plants and animals. They use formal systems to recognize the discovery of new species and relate them to their classification scheme. Computer network administrators strive to document and communicate the design, implementation and maintenance of their networks including their nodes and connections using network diagrams and other tools and thus they must define each node, the connections (edges) between nodes and their orientations in some cases.
One method for representing complex systems is termed xe2x80x9cexpositionxe2x80x9d, using text to convey relationships. Using text to convey an understanding of relationships between entities is pervasive. For example, in the sentence: xe2x80x9cPrince Charles is the son of Queen Elizabeth II.xe2x80x9d, a relationship between two entities is presented. Exposition is limited as a way of representing complex systems because of the large number of words, which would be necessary to describe and represent even a small number of relationships. Another limitation of exposition is that any mental pictures of the system are left to the listener or reader. Of course, textual exposition has the advantage of being easily communicated. Exposition is considered a linear (xe2x80x9cone-dimensionalxe2x80x9d) data type of information visualization.
Another method used to display complex systems or relationships is termed xe2x80x9ctabulationxe2x80x9d. Tables A and B provide an example of tabulation. FIG. 1 shows a graphical representation of a directed graph. Tables A and B provide the same information, albeit in a less graphical form.
The directed graph may be conceptualized as tables representing the collections of a graph G=(V,E). In the above example, Tables A and B represent the nodes in the graph and the collection of edges, respectively. Each element (row) of Table A provides an ID (a unique numeric identifier for the node) and a Name (a unique name or label applied to the node). Each element (row) of Table B provides an ID (a unique numeric identifier for the edge), a Name (a unique name or label indication of the initial node and terminal node for the edge.
Tabulation can be used to accurately reflect the nature of complex systems. As with exposition the mental picture of the underlying system is left to the reader.
Yet another method of representing a system is an outline. An example of outlining is an outline of a speech, where the speech is organized into the major headings of an introduction, a body and a conclusion. Under each of those major headings, words or phrases capturing the essence of the points to be made in those sections are listed under the major heading and indented. While traditional outlining uses a numbering scheme, another form of outlining, nested bullet lists, demonstrates that the indentation of sub-points below main points conveys the nature of the relationship between the sub-headings and their parent headings. An outline represents the relationships between the outline""s headings and subheadings, subheadings and sub-subheadings and so forth. Because of its nature and common uses, outlining is confined to representing sets of relationships that are hierarchical and organizable into a tree structure with a single root. This hierarchical nature is also called xe2x80x9csingle inheritancexe2x80x9d. Outlining is generally considered to be a powerful tool for understanding, modeling and organization, but outlines or tree structures can not represent arbitrarily complex systems or arbitrary directed graphs. Conversely, however, a directed graph can represent an outline or tree structure.
One prior art method of displaying data about relationships on a computer display device is an outline control (or xe2x80x9cwidgetxe2x80x9d), also called a xe2x80x9ctreexe2x80x9d control or xe2x80x9ctree viewxe2x80x9d control. And as implied by the name, such controls are limited to displaying trees or outlines which are hierarchies. An example of the use of an outline control is the file dialog program used to visually represent the directories and files within computer systems. Most computer operating systems employ a hierarchical organization of their files, so these controls do a complete and accurate job of representing the relationships of the directories, subdirectories and files. In addition to the basic outline representation, the user has the ability to expand and contract or zoom in and zoom out on the view of structures and substructures. In a specific embodiment of such a control, a plus-sign (xe2x80x9c+xe2x80x9d) is placed in front of the entity which has its subtree contracted. This shows that an expansion is possible and clicking on that plus-sign object will cause an expansion of the subtree. Once expanded, the control shows the child entities by listing them below and indented and often connected with lines. These now exposed entities may have additional child entities associated to them, which may also be capable of expansion, and so on.
From an information visualization perspective, items in a tree view can have only one parent and no item can have a subset which contains itself. Thus, a limitation of outline or tree controls is that they can on1y represent hierarchical or tree relationships.
Another method used to model complex systems is Entity-Relationship (ER) diagramming. Variations of ER diagramming are used for a variety of database design and system engineering methods, Computer Aided System Engineering (CASE) tools and for other disciplines. These variations comprise different constructs and employ different diagrammatic notations but share elemental concepts. In an ER diagram, an entity (or object, thing, class, node, etc.) and the relationship (or relation, association, connection or association) are displayed.
ER diagramming has many variations, but generally, entities are represented as bounded figures, such as rectangles, circles or rounded rectangles and relationships are represented as lines or arcs drawn between pairs of entities. Entities are generally labeled with a name and relationships are labeled with a phrase representing the nature of the relationship. ER diagrams can contain additional information about the entities and relationships represented. An ER diagram can be represented as a pictorial directed graph and is generally modeled mathematically as a directed graph. In an ER diagram, there is no implicit parentage or superiority of one entity over another, nor is there an implicit root, starting point or focus of attention.
ER diagramming has several disadvantages, such as requiring relatively large amounts of space to present each entity compared to a textual list, a difficulty following the lines (relationships) between entities as the number of relationships increase, the difficulty of revising the ER diagram as the underlying system changes and the lack of an implicit focus or perspective for the user.
As with most graphical presentations, emphasis can be placed on one element over another. For example, centrally locating the most important entity might be a way to emphasize that entity and locating important entities around that entity might be a way to emphasize their relative importance. However, the user of the graphic presentation may have interest in some other entity or relationship and wish to emphasize that entity or relationship over another at one time and not at another. Without at least some redrawing, this might not be possible with an ER diagram.
When ER diagrams are computerized for computerized display, most of the drawbacks are still present. Even revisions can cause the user to move entities around and make tradeoffs of the overall presentation. Much of the effort in preparing ER diagrams is expended to direct the program where to place entities, what size they should be, whether page breaks should occur and various other aesthetic and practical considerations. Some computerized ER diagramming tools provide for automatic placement of elements, but the results may not be satisfactory. If the complex system being modeled is dynamic and it is desirable for the model to be dynamic, the resources required for graphical presentation can be burdensome. Another shortcoming of automated ER diagramming relates to the communication of the data necessary to produce a graph electronically. Much of the data necessary for storage of automated ER diagrams relates to the graphical nature and thus is more resource intensive when the information is to be communicated.
Complex systems can be represented by network diagrams, with similar disadvantages. As with ER diagramming, a network diagram is graphical, often using circles to represent nodes of a network and lines to represent connections. Network diagrams are closely related to directed graphs, but are usually represented as undirected graphs. A network node is analogous to a directed graph node and a connection is analogous to an edge. Network diagrams can be represented by directed graphs. Complex system models can also be represented on computer devices using a network diagramming program. Network diagramming programs, methods and apparatus have the same shortcomings as ER diagramming.
Numerous other methods for depicting directed graphs and their computer implementations exist, however they all share, to varying degrees, similar shortcomings with ER diagramming.
In one embodiment of a display system according to the present invention, an arbitrarily complex system is represented by a xe2x80x9cwordgraphxe2x80x9d structure on a computer output device, such as an interactive display or a printed output. A wordgraph is a multi-dimensional outline representing a subset of a directed graph with a given starting node with each edge related to a node in one direction (either incident into the node or incident out of the node) being indented in one direction relative to the node and edges related to the node in the other direction being indented in another direction. For example, the edges related in one direction might be above the node and the edges related in the other direction might be below the node.
Any node from the collection of nodes can be used as the starting node of the displayed wordgraph. The display system can display, or prepare for subsequent display, a node as a text string, alone, implied or with any other information configured by the user to appear with the node as a string. This string might be placed at the lowest level, at the left hand margin of the conceptual or actual textual display.
The display system might present an edge from a presented node by presenting the terminal node of the edge on a line below the presented node and indented one level. In so doing, the display system assigns a level of one greater than the current level to the presented node. If any edges are incident into the presented node, those edges are presented by showing the initial node of each such edge on a line above the presented node and indented one level in a unique way such that it is recognizable as being an edge incident into the presented node in a way opposite of those having been place below the presented node. Edges incident into a node are thus distinguished from edges incident out of that node.